

package mvcc

import (
	"bytes"
	"errors"
	"fmt"

	"github.com/google/btree"
	"go.uber.org/zap"
)

var (
	ErrRevisionNotFound = errors.New("mvcc: revision not found")
)

// keyIndex在后端存储密钥的修订。
// 每个密钥索引至少有一个密钥生成。
// 每一代可能有几个关键版本。
// 键上的墓碑在当前一代的结尾追加墓碑版本
// 并创建新的空一代。
// 每个版本的密钥都有一个指向后端的索引。
// 
// 例如：put（1.0）；put（2.0）；墓碑（3.0）；put（4.0）；墓碑（5.0）上的键“foo”
// 生成一个键索引：
// 键：“foo”
// 版本：5 
// 世代：
// /{empty}
// /{4.0,5.0（t）}
// 
// Compact a keyIndex将删除除最大版本外的小于或等于
// rev的版本。如果在压缩过程中生成内容变为空
// 则将其删除。如果所有代都被
// 删除，则应该删除keyIndex。
// 
// 例如：
// 在上一个示例上压缩（2）
// 世代：
// /{empty}
// /{4.0,5.0（t）}
// /{4.0,5.0（t）}
// /
// /紧凑型（5）：
// /代：
// /{empty}->密钥应被删除。
// 
// compact（6）：
// 世代：
// /{empty}->应删除密钥。

type keyIndex struct {
	key         []byte	// 客户端提供的原始Key值。
	// revision中还提供了排序、比较（GreaterThan（）方法）、序列化等相关的方法
	modified    revision // 记录该Key值最后一次修改对应的revision信息
	// 当第一次创建客户端给定的Key值时，对应的第O代版本信息（即generations[O］项〉也会被创建，
	// 所以每个Key值至少对应一个generation实例（如果没有，则表示当前Key值应该被删除〉，
	// 每代中包含多个reversion信息。当客户端后续不断修改该K巳y时，generation[O］中会不断追加revision信息
	generations []generation
}

// keyIndex. put（）方法，该方法负责向keyIndex中追加新的revision信息
func (ki *keyIndex) put(lg *zap.Logger, main int64, sub int64) {
	// 根据传入的mainreversion和subreversion创建reversion实例
	rev := revision{main: main, sub: sub}
	// 检测该reversion实例的合法性
	if !rev.GreaterThan(ki.modified) {
		lg.Panic(
			"'put' with an unexpected smaller revision",
			zap.Int64("given-revision-main", rev.main),
			zap.Int64("given-revision-sub", rev.sub),
			zap.Int64("modified-revision-main", ki.modified.main),
			zap.Int64("modified-revision-sub", ki.modified.sub),
		)
	}
	if len(ki.generations) == 0 {	// 创建generat工ons[O］实例
		ki.generations = append(ki.generations, generation{})
	}
	g := &ki.generations[len(ki.generations)-1]
	if len(g.revs) == 0 { // 新建Key，则初始化对应generation实例的created字段
		keysGauge.Inc()
		g.created = rev
	}
	g.revs = append(g.revs, rev)	// 向generation.revs中追加revision信息
	g.ver++	// 递增generation.ver
	ki.modified = rev	// 更新keyindex.modified字段
}

// key Index.restore（）方法负责恢复当前的keylndx中的信息
func (ki *keyIndex) restore(lg *zap.Logger, created, modified revision, ver int64) {
	if len(ki.generations) != 0 {
		lg.Panic(
			"'restore' got an unexpected non-empty generations",
			zap.Int("generations-size", len(ki.generations)),
		)
	}

	ki.modified = modified
	// 创建generation实例，并添加到generations中
	g := generation{created: created, ver: ver, revs: []revision{modified}}
	ki.generations = append(ki.generations, g)
	keysGauge.Inc()
}

// keyIndex. tombstone（）方法，
// 该方法会在当前generation中追加一个revision实例，然后新建一个generation实例，
func (ki *keyIndex) tombstone(lg *zap.Logger, main int64, sub int64) error {
	// 检测当前的keyindex.generations字段是否为空，以及当前使用的generation实例是否为空
	if ki.isEmpty() {
		lg.Panic(
			"'tombstone' got an unexpected empty keyIndex",
			zap.String("key", string(ki.key)),
		)
	}
	if ki.generations[len(ki.generations)-1].isEmpty() {
		return ErrRevisionNotFound
	}
	ki.put(lg, main, sub)	// ，在当前generation中追加一个revision
	// 在generat工0口5中创建新generation实例
	ki.generations = append(ki.generations, generation{})
	keysGauge.Dec()
	return nil
}

// key Index.get（）方法会在当前keyIndex实例中查找小于指定的main revision的最大revision
func (ki *keyIndex) get(lg *zap.Logger, atRev int64) (modified, created revision, ver int64, err error) {
	// 检测当前keyinde中是否记录了generation实例
	if ki.isEmpty() {
		lg.Panic(
			"'get' got an unexpected empty keyIndex",
			zap.String("key", string(ki.key)),
		)
	}
	// 根据给定的main revision，查找对应的generation实例，如采没有对应的generation，则报错
	g := ki.findGeneration(atRev)
	if g.isEmpty() {
		return revision{}, revision{}, 0, ErrRevisionNotFound
	}
	// 在generation中查找对应的revision实例，如采查找失败，就会报错
	n := g.walk(func(rev revision) bool { return rev.main > atRev })
	if n != -1 {
		// 返回值除了目标rev工S工on实例，还有该Key此次创建的revision实例，以及到目标revision之前的修改次数
		return g.revs[n], g.created, g.ver - int64(len(g.revs)-n-1), nil
	}

	return revision{}, revision{}, 0, ErrRevisionNotFound
}

// since（）方法用于批量查找revision，该方法负责返回当前keyIndex 实例中main部分大于指定值的revision实例，
// 如果查询结果中包含了多个main部分相同的revision实例，则只返回其中sub部分最大的实例。
func (ki *keyIndex) since(lg *zap.Logger, rev int64) []revision {
	if ki.isEmpty() {
		lg.Panic(
			"'since' got an unexpected empty keyIndex",
			zap.String("key", string(ki.key)),
		)
	}
	since := revision{rev, 0}
	var gi int
	// 倒序运历所有generation实例，查询从哪个generation开始查找（fifgi对应的generation实例）
	for gi = len(ki.generations) - 1; gi > 0; gi-- {
		g := ki.generations[gi]
		if g.isEmpty() {
			continue
		}
		// 比较创建当前generation实例的revision与since
		// 在generation.GreaterThan（）方法中会先比较mainrevision部分，
		// 如果相同，则比较subrevision部分
		if since.GreaterThan(g.created) {
			break
		}
	}

	var revs []revision	// 记录返回结果
	var last int64	// 用于记录当前所遇到的最大的mainrevision值
	for ; gi < len(ki.generations); gi++ {	// 从gi处开始遥历generation实例
		for _, r := range ki.generations[gi].revs {	// 边历每个generation中记录的revision实例
			if since.GreaterThan(r) {	// 忽略main revision部分较小的revisioη实例
				continue
			}
			// 如果查找到rnainrevision部分相同且subrevision更大的revision实例，
			// 则用其替换之前记录的返回结果，从而实现main部分相同时只返回sub部分较大的revision实例
			if r.main == last {
				revs[len(revs)-1] = r
				continue
			}
			revs = append(revs, r)	// 将符合条件的revision实例记录到revs中
			last = r.main	// 更新last
		}
	}
	return revs
}

// 随着客户端不断修改键值对，keyIndex中记录的revision实例和generation实例会不断增加，
// 我们可以通过调用compact（）方法对keyIndex进行压缩。在压缩时会将main部分小于指定值的全部revision实例全部删除。
// 在压缩过程中，如果出现了空的generation实例，则会将其删除。
// 如果keylndx中全部的generation实例都被清除了，则该keyIndex实例也会被删除
func (ki *keyIndex) compact(lg *zap.Logger, atRev int64, available map[revision]struct{}) {
	if ki.isEmpty() {
		lg.Panic(
			"'compact' got an unexpected empty keyIndex",
			zap.String("key", string(ki.key)),
		)
	}

	genIdx, revIndex := ki.doCompact(atRev, available)

	g := &ki.generations[genIdx]
	// 追历目标generation中的全部rev工sion实例，清空目标generation实例中main部分小于指定位的revision
	if !g.isEmpty() {
		// 删除以前的内容。
		if revIndex != -1 {
			g.revs = g.revs[revIndex:]	// 清理目标generation
		}
		// 如采目标generation实例中只有tombstone,Jil1J将其删除
		if len(g.revs) == 1 && genIdx != len(ki.generations)-1 {
			delete(available, g.revs[0])
			genIdx++	// 递增genIdx，后面会清理工之前的全部generat工on实例
		}
	}

	// 清理目标generation实例之前的全部generation实例
	ki.generations = ki.generations[genIdx:]
}

// keep查找在给定atRev调用compact时要保留的修订。
func (ki *keyIndex) keep(atRev int64, available map[revision]struct{}) {
	if ki.isEmpty() {
		return
	}

	genIdx, revIndex := ki.doCompact(atRev, available)
	g := &ki.generations[genIdx]
	if !g.isEmpty() {
		// 移除任何墓碑
		if revIndex == len(g.revs)-1 && genIdx != len(ki.generations)-1 {
			delete(available, g.revs[revIndex])
		}
	}
}

func (ki *keyIndex) doCompact(atRev int64, available map[revision]struct{}) (genIdx int, revIndex int) {
	f := func(rev revision) bool {	// 后面遍历generation时使用的回调函数
		if rev.main <= atRev {
			available[rev] = struct{}{}
			return false
		}
		return true
	}

	genIdx, g := 0, &ki.generations[0]
	// 追历所有的generation实例，目标generation实例中的tombstone大于指定的revision
	for genIdx < len(ki.generations)-1 {
		if tomb := g.revs[len(g.revs)-1].main; tomb > atRev {
			break
		}
		genIdx++
		g = &ki.generations[genIdx]
	}

	revIndex = g.walk(f)

	return genIdx, revIndex
}

func (ki *keyIndex) isEmpty() bool {
	return len(ki.generations) == 1 && ki.generations[0].isEmpty()
}

// findGeneration查找给定修订所属的键索引的生成。如果给定的版本间隔为两代，
// 这意味着给定版本中不存在密钥，则返回nil。
func (ki *keyIndex) findGeneration(rev int64) *generation {
	lastg := len(ki.generations) - 1
	cg := lastg	// 指向当前keyIndex实例中最后一个generation实例，并逐个向前查找

	for cg >= 0 {
		if len(ki.generations[cg].revs) == 0 {	// 过滤调用空的generation实例
			cg--
			continue
		}
		g := ki.generations[cg]
		if cg != lastg {	// 如果不是最后一个generation实例，则先与tombonerevision进行比较
			if tomb := g.revs[len(g.revs)-1].main; tomb <= rev {
				return nil
			}
		}
		if g.revs[0].main <= rev {	// 与generation中的第一个revision比较
			return &ki.generations[cg]
		}
		cg--
	}
	return nil
}

func (ki *keyIndex) Less(b btree.Item) bool {
	return bytes.Compare(ki.key, b.(*keyIndex).key) == -1
}

func (ki *keyIndex) equal(b *keyIndex) bool {
	if !bytes.Equal(ki.key, b.key) {
		return false
	}
	if ki.modified != b.modified {
		return false
	}
	if len(ki.generations) != len(b.generations) {
		return false
	}
	for i := range ki.generations {
		ag, bg := ki.generations[i], b.generations[i]
		if !ag.equal(bg) {
			return false
		}
	}
	return true
}

func (ki *keyIndex) String() string {
	var s string
	for _, g := range ki.generations {
		s += g.String()
	}
	return s
}

// 生成包含一个密钥的多个修订。
type generation struct {
	ver     int64	// 记录当前gen巳ration所包含的修改次数，即revs数组的长度。
	created revision // 记录创建当前generation实例时对应的revision信息。
	revs    []revision	// 当客户端不断更新该键值对时，revs数组会不断追加每次更新对应revision信息。
}

func (g *generation) isEmpty() bool { return g == nil || len(g.revs) == 0 }

// 查找从该gener创ion实例中查找符合条件的revision实例
func (g *generation) walk(f func(rev revision) bool) int {
	l := len(g.revs)
	for i := range g.revs {
		ok := f(g.revs[l-i-1])	// 逆序查找generation.revs数纽
		if !ok {
			return l - i - 1	// 返回目标revision的下标
		}
	}
	return -1
}

func (g *generation) String() string {
	return fmt.Sprintf("g: created[%d] ver[%d], revs %#v\n", g.created, g.ver, g.revs)
}

func (g generation) equal(b generation) bool {
	if g.ver != b.ver {
		return false
	}
	if len(g.revs) != len(b.revs) {
		return false
	}

	for i := range g.revs {
		ar, br := g.revs[i], b.revs[i]
		if ar != br {
			return false
		}
	}
	return true
}
